`
https://leetcode.cn/problems/regular-expression-matching/
`

/**
 * @param {string} s
 * @param {string} p
 * @return {boolean}
 */
var isMatch = function (s, p) {
  // 缓存结果，避免重复计算
  // memo[i][j] 表示 s[i...] 是否能匹配 p[j...]
  // memo[i][j] = -1 表示没有计算过，0 表示 false，1 表示 true
  const memo = new Array(s.length).fill().map(() => new Array(p.length).fill(-1))

  // 定义：dp(i, j) 表示 s[i...] 是否能匹配 p[j...]
  function dp(i, j) {
    // 如果 p 匹配完了，看看 s 是否也匹配完了
    if (j === p.length) {
      return i === s.length
    }

    // 如果 s 匹配完了，看看 p 剩下的是不是只剩可以被忽略的通配符了
    if (i === s.length) {
      if ((p.length - j) % 2 === 1) {
        return false;
      }
      for (; j + 1 < p.length; j += 2) {
        if (p[j + 1] !== '*') {
          return false;
        }
      }
      return true;
    }

    // 已经计算过
    if (memo[i][j] !== -1) {
      return memo[i][j]
    }

    // 能匹配
    if (s[i] === p[j] || p[j] === '.') {
      // 遇到通配符 *
      if (j < p.length - 1 && p[j + 1] === '*') {
        // 匹配 0 次或多次
        memo[i][j] = dp(i, j + 2) || dp(i + 1, j)
      } else {
        // 正常匹配
        memo[i][j] = dp(i + 1, j + 1)
      }
    } else {
      // 不匹配
      if (j < p.length - 1 && p[j + 1] === '*') {
        // 跳过通配符 *
        memo[i][j] = dp(i, j + 2)
      } else {
        // 无法继续匹配
        memo[i][j] = false
      }
    }

    return memo[i][j]
  }

  return dp(0, 0)
};